package leetcode_1501_1600;

public class LeeCode_1537 {
    public static void main(String[] args) {
        System.out.println(maxSum(new int[]{2, 4, 5, 8, 10}, new int[]{4, 6, 8, 9}));
        System.out.println(maxSum(new int[]{1,2,3}, new int[]{4,5,6}));
    }
    private static int maxSum(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        long mod = (long) (1e9 + 7);
        int i2 = n - 1, i1 = m - 1;
        long[][] dp = new long[2][Math.max(m, n) + 1];
        while (i1 >= 0 && i2 >= 0){
            if (nums1[i1] == nums2[i2]){
                dp[0][i1] = Math.max(dp[0][i1 + 1], dp[1][i2 + 1]) + nums1[i1];
                dp[1][i2] = Math.max(dp[1][i2 + 1], dp[0][i1 + 1]) + nums2[i2];
                i1--;
                i2--;
            }else if (nums1[i1] > nums2[i2]){
                dp[0][i1] = dp[0][i1 + 1] + nums1[i1];
                i1--;
            }else {
                dp[1][i2] = dp[1][i2 + 1] + nums2[i2];
                i2--;
            }
        }
        while (i1 >= 0){
            dp[0][i1] = dp[0][i1 + 1] + nums1[i1];
            i1--;
        }
        while (i2 >= 0){
            dp[1][i2] = dp[1][i2 + 1] + nums2[i2];
            i2--;
        }
        return (int) (Math.max(dp[0][0], dp[1][0]) % mod);
    }
}